//import BinomialHeap.BinomialHeapTree;

/**
 * BinomialHeap
 *
 * An implementation of lazy binomial heap over non-negative integers.
 * 
 * @inv: isValid
 * @impInv: n == no. of elements in the heap
 * @impInv: min == element in heap with min key 
 */
public class BinomialHeap
{
	private Node min;  
	private int n;   //the number of nodes in the heap
	
   /**
    * public boolean empty()
    *
    * precondition: none
    * 
    * The method returns true if and only if the heap
    * is empty.
    *   
    */
    public boolean empty()
    {
    	return min == null;
    }
		
   /**
    * public void insert(int value)
    *
    * Insert value into the heap 
    * 
    */
    public void insert(int value) 
    {    
    	Node newNode = new Node();
    	newNode.degree = 0;
    	newNode.child = null;
    	newNode.key = value;
    	newNode.left = newNode;
    	newNode.right = newNode;
    	BinomialHeap children = new BinomialHeap();
     	children.min = newNode;
     	children.n = 1;
     	meld(children);
    	if(newNode.key < min.key)
    	{
    		min = newNode;
    	}
    }

   /**
    * public void deleteMin()
    *
    * Delete the minimum value if there is any values in the heap, or does nothing otherwise
    *
    */
    public void deleteMin()
    {
     	if (!empty())
     	{
     		Node curMin = min;
     		BinomialHeap children = new BinomialHeap();
     		children.min = min.child;
     		children.n = 0;   //the children are already counted in this.n
 
     		meld(children);
     		
     		curMin.right.left = curMin.left;
     		curMin.left.right = curMin.right;
     		
     		if (curMin == curMin.right) //i.e. $prev(this.n)=1
     		{
     			min = null;
     		}
     		else
     		{
     			min = curMin.right;
     			consolidate();
     		}
     		n--;
     	}
    }

   /**
    * public int findMin()
    *
    * Return the minimum value
    * 
    * precondition: !empty();
    *
    */
    public int findMin()
    {
    	return min.key;
    } 
    
   /**
    * public void meld (BinomialHeap heap2)
    *
    * Meld the heap with heap2
    * 
    * precondition: heap2!=null
    * postcondition: adds all the trees in heap2 to this binomialHeap, (and updates the class members)
    *
    */
    public void meld (BinomialHeap heap2)
    {
    	//special cases
    	if (heap2.empty()){return;}
    	if (this.empty()){
    		this.min=heap2.min; 
    		this.n=heap2.n; 
    		return;	
    	}    	
    	//general case
    	  Node first1=this.min;
    	  Node first2=heap2.min;
    	  Node last1=this.min.left;
    	  Node last2=heap2.min.left;
    	  
    	  first1.left=last2;
    	  last2.right=first1;
    	  first2.left=last1;
    	  last1.right=first2;
    	  if (this.min.key>heap2.min.key){
    		  this.min=heap2.min;
    	  }
    	  this.n+=heap2.n;
    }

   /**
    * public int size()
    * Return the number of elements in the heap
    *
    * precondition: true;
    * postcondition: Returns the number of elements in the heap
    * 
    */
    public int size()
    {
    	return n;
    }
    
   /**
    * public int[] treesSize()
    *
    * Return an array containing the ranks of the trees that represent the heap
    * in ascending order.
    * 
    * precondition: true;
    * postcondition: $ret is a sorted array of the heap trees ranks (rank==degree)
    * 
    */
    public int[] treesRanks()
    {        	    	
    	if (empty()){
    		return new int[0];
    	}
    	int[] countSortArr=new int[(int) Math.floor(Math.log(n)/Math.log(2))+1];  
    	//counts the no. of trees of each rank, and also counts the no. of trees in the heap
    	Node x=min;
    	int numOfTrees=0;
        do {
        	countSortArr[x.degree]++;
        	numOfTrees++;
        	x=x.right;
        } while (x!=min);
        
        //generate result array
    	int[] result=new int[numOfTrees];
        
        int index=0;
        for (int i=0;i<countSortArr.length;i++){
        	for (int j=0;j<countSortArr[i];j++){
        		result[index]=i;
        		index++;
        	}
        }
        return result;
    }

   /**
    * public boolean isValid()
    *
    * Returns true if and only if the heap is valid. i.e if each tree is a binomial tree, and follows the heap rule
    * can show with induction that if the root has d children which are in themselves binomial trees of degrees 0,1,...,d-1 that the tree is binomial tree
    */
    public boolean isValid() 
    {
    	if (min == null){
    		return true;
    	}
    	// go throw all the trees in the heap
    	Node curTree = min;
    	int deg = getNoOfChildren(curTree);
    	do
		{
			if (!isBinomyTree(curTree, deg))
			{
				return false;
			}
			curTree = curTree.right;
			deg = getNoOfChildren(curTree);
		} while(!curTree.equals(min));
    	return true;
    }

    
   /**
    * public class Node
    * 
    * represents a Node in a binomialHeap (each Node is a root of a binomial tree) 
    */
    public class Node{
    	private Node child;    // a pointer to the highest degree child
    	private Node left; 		    
    	private Node right;
    	private int key;
    	private int degree;//the rank of the binomial tree that this Node is its root [degree==rank]
    	
    	//comment: if (this.right!=this.p.child) then this.right.degree<this.degree; e.g. the circular list is in decsending order (of degree), starting at this.p.child)
    	
    	//for debug only
    	public String toString(){
    		return Integer.toString(left.key)+" - " + Integer.toString(key) +" - "+ Integer.toString(right.key); 
    	}

    }
    
    //////////////private methods (Added)/////////////////////////////////////////////
    
    /**
     * private void consolidate()
     * 
     * Perform "successive linking" after a node has been deleted
     * 
     * precondition (imp): called from within deleteMin() //maybe not necessary, but why not :)   
     * postcondition: $ret(treesRanks) has no repetitions
     */
    private void consolidate(){
    	Node[] A=new Node[(int) Math.floor(Math.log(n)/Math.log(2))+1];
    	
    	//first generate an array which cells point to the binomial trees roots according to original order
    	int numOfRoots=0;
    	Node w=min;
    	do{
    		numOfRoots++;
    		w=w.right;
    	}while (w!=min);
    	
    	Node[] roots=new Node[numOfRoots];
    	for (int i=0;i<roots.length;i++){
    		roots[i]=w;
    		w=w.right;
    	}
    	
    	//now traverse all the roots and link if needed
    	for(Node r: roots){	
    		Node x=r;
    		int d=x.degree;
    		while (A[d]!=null){
    			Node y=A[d];    //another node with the same degree as x
    			if (x.key>y.key){
    				//exchange x with y
    				Node temp=x;
    				x=y;
    				y=temp;
    			}
    			binomialLink(y,x);
    			A[d]=null;
    			d++;
    		}
    		A[d]=x;
    	}
    	
    	//Reestablish the root list that points by min
    	this.min=null;
    	for (int i=0;i<A.length;i++){
    		if (A[i]!=null){  
    			if (min==null){
    				min=A[i];
    				min.left=min;
    				min.right=min;
    			}else{
    				Node temp=min.right;
    				min.right=A[i];
    				A[i].left=min;
    				temp.left=A[i];
    				A[i].right=temp;
    				
    				if (A[i].key<min.key){
    					min=A[i];
    				}
    			}
    		}
    	}
    }
    
    /**
     * private void binomialLink(Node y, Node x){
     * 
     * Hung the BinomialHeapTree rooted in Node y on the root of BinomialHeapTree x
     * 
     * precondition: x and y are roots of binomial trees in the heap && x.degree==y.degree
     * postcondition: y is not a tree root in the heap && y is a child of x && x.degree is incremented
     */
    
    private void binomialLink(Node y, Node x){
    	//remove y from the root list
    	Node left=y.left;
    	Node right=y.right;
    	
    	left.right=right;
    	right.left=left;
    	if (x.child==null){
    		y.left=y;
    		y.right=y;
    	}else{
    	Node lastChild=x.child.left;
    	y.right=x.child;
    	x.child.left=y;
    	y.left=lastChild;
    	lastChild.right=y;
    	}
    	x.child=y;
    	x.degree++;
    }


    /**
     * private boolean isBinomyTree(Node curTree , int degree)
     *
     * @pre: curTree!=null && degree is the no. of children Nodes of curTree;
     * @post: Returns true if and only if the tree rooted in curTree is a BinomyTree of degree deg; 
     *   
     */
    private boolean isBinomyTree(Node curTree , int degree) {
    	if(degree == 0)
    	{
    		return true;
    	}
    	Node temp = curTree.child;
    	boolean[] treeChildDeg = new boolean[degree];
    	int treeDeg;
    	
    	do {
    		if (temp==null){
    			return false;
    		}
    		if (temp.key<curTree.key){
    			return false;
    		}
    		treeDeg = getNoOfChildren(temp);
    		if (!isBinomyTree(temp, treeDeg))
    		{
    			return false;
    		}
    		if(treeDeg >= degree || treeChildDeg[treeDeg] == true)  //two children from the same degree
    		{
    			return false;
    		}
    		else
    		{
    			treeChildDeg[treeDeg] = true;
    		}
    		temp = temp.left;
    	} while(temp != curTree.child);
    	return arrChildTrue(treeChildDeg);
    }
    
    /**
     * private boolean arrchildTrue(boolean[] treeChildDeg) 
     *
     * check if all the entries of treeChildDeg are true
     * 
     * @pre: treeChildDeg!=null
     * @pose: returns true iff all the entries in treeChildDeg are true;
     *  
     *   
     */
    private boolean arrChildTrue(boolean[] treeChildDeg) {
    	for (boolean i: treeChildDeg){
    		if (i==false){
    			return false;
    		}
    	}
    	return true; 
    }

    /**
     * private int getNoOfChildren(Node start)
     *
     * return the no. of children of start
     * 
     * @pre: start!=null
     * @post: Returns the number of child that start have
     *   
     */
	private int getNoOfChildren(Node start) {
    	if (start.child == null)
    	{
    		return 0;
    	}
    	int counter = 1;
    	Node temp = start.child.right;
    	while(temp != start.child)
    	{
    		counter++;
    		temp = temp.right;
    	}
    	//System.out.println("start " + start.degree + " counter " + counter);
    	return counter;
    }

}
